/*
 * One example for NOI CSP-J Lesson 10:
 * <https://courses.fmsoft.cn/plzs/noijunior-csp-exercises-lower.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <climits>
#include <cassert>

using namespace std;

using ll_t = long long;
using adj_list = vector<vector<pair<int, int>>>;

// 从指定顶点处递归执行 DFS
void dfs(adj_list &graph, stack<int>& path, vector<bool> &visited,
        int start, int stop, int k, ll_t time_open, ll_t time_start, ll_t& ans)
{
    if (start == stop) {
        // 到达景区出口。

        clog << "Reach exit " << time_start << "; path length: " << path.size() << endl;
        if (path.size() % k == 0) {
            clog << "Find a path!" << endl;

            ll_t time_reach = time_start + path.size();

            ll_t time_inc = 0;
            if (time_reach < time_open) {
                // 调整出发时间。
                time_inc = ((time_open - time_reach + k - 1)/k) * k;
            }
            time_start += time_inc;
            time_reach += time_inc;

            clog << "Got a path: " << time_reach << endl;
            // 这条道路满足条件。
            if (ans > time_reach)
                ans = time_reach;
        }

        return;
    }

    // 标记当前顶点已被访问
    visited[start] = true;

    // 将当前顶点压入栈
    path.push(start);

    ll_t time_reach = time_start + path.size();

    // 递归访问所有尚未被访问的邻接顶点
    for (auto &i : graph[start]) {
        int v = i.first;
        ll_t a = i.second;

        if (visited[v] == false) {

            ll_t time_inc = 0;
            if (time_reach < a) {
                // 调整出发时间。
                time_inc = ((a - time_reach + k - 1)/k) * k;
                assert((time_start + time_inc) % k == 0);
            }

            clog << "edge: " << start << " -> " << v << " open time: " << a << endl;
            dfs(graph, path, visited, v, stop, k, a, time_start + time_inc, ans);
            if (v != stop) {
                path.pop();
            }
        }
        else {
            clog << start << " -> " << v << " visited " << endl;
        }
    }
}

ll_t resolve(adj_list& graph, int k, int start, int stop)
{
    ll_t time_start = 0LL;
    ll_t ans = LLONG_MAX;

    vector<bool> visited(graph.size(), false);
    stack<int> path;

    dfs(graph, path, visited, start, stop, k, 0, time_start, ans);

    if (ans == LLONG_MAX)
        return -1;

    return ans;
}

int main()
{
    adj_list graph(5 + 1);
    graph[1].push_back({2, 0});
    graph[2].push_back({5, 1});
    graph[1].push_back({3, 0});
    graph[3].push_back({4, 3});
    graph[4].push_back({5, 1});

    int ans;
    ans = resolve(graph, 3, 1, 5);
    clog << ans << endl;
    assert(ans == 6);

    int n, m, k;
    cin >> n >> m >> k;
    adj_list graph2(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, a;
        cin >> u >> v >> a;
        graph2[u].push_back({v, a});
    }

    ans = resolve(graph2, k, 1, n);
    cout << ans << endl;
    return 0;
}

